/*
** 3D Engine Code by Neil C. Obremski                         [ Magenta's Maze ]
** 2017 Gibdon Moon Productions                   [ http://magsmaze.gibdon.com ]
**
** This is free and unencumbered software released into the public domain.
**
** Anyone is free to copy, modify, publish, use, compile, sell, or
** distribute this software, either in source code form or as a compiled
** binary, for any purpose, commercial or non-commercial, and by any
** means.
**
** In jurisdictions that recognize copyright laws, the author or authors
** of this software dedicate any and all copyright interest in the
** software to the public domain. We make this dedication for the benefit
** of the public at large and to the detriment of our heirs and
** successors. We intend this dedication to be an overt act of
** relinquishment in perpetuity of all present and future rights to this
** software under copyright law.
**
** THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
** EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
** MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
** IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR
** OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
** ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
** OTHER DEALINGS IN THE SOFTWARE.
**
** Tested w/ DOSBox 0.74, Microsoft C 5.10
 */
#ifndef __MAG_3D
#define __MAG_3D

#include <string.h>		/* memset() */

#include "mag-math.h"	/* fixed point functions */

/* globals */
int VD = 7;			/* view distance in BITS (SHL to multiply) */
int HITHER = 25;	/* near clipping plane */
int YON = 500;		/* far clipping plane */
int OX = 160;		/* origin X */
int OY = 100;		/* origin Y */

/* 3D point / vertex / vector */
struct vertex {
	int x, y, z;
};

#define VERT_IS_NULL(v) (0x7FFF == (v).x)

#define VERT_NOT_NULL(v) (0x7FFF != (v).x)

#define VERT_MAKE_NULL(v) ((v).x = (v).y = (v).z = 0x7FFF)

/* U texture coordinate based on vertex index (0 or 15) */
#define VERT_U(vi) (0 == (vi) || 3 == (vi) ? 0 : 15)
#define VERT_U_FX(vi) (0 == (vi) || 3 == (vi) ? 0L : 253952L)

/* V texture coordinate based on vertex index (0 or 15) */
#define VERT_V(vi) (vi < 2 ? 0 : 15)
#define VERT_V_FX(vi) (vi < 2 ? 0L : 253952L)

/* 3D polygon poly (v4 overloaded for border bits in triangles) */
struct polygon {
	char v1, v2, v3, v4;	/* vertex indices */
	char nx, ny, nz;		/* unit normal vector (2.6 FX) */
	char shw;				/* SHoW? */
};

#define POLY_IS_NULL(t) ((char)-1 == (t).v1)

#define POLY_MAKE_NULL(t) ((t).v1 = (t).v2 = (t).v3 = (char)-1)

#define POLY_NOT_NULL(t) ((t).v1 >= (char)0)

/* 3D object (no pointers allows for shallow memory copy) */
#define MESH_POLY_MAX (char)16
#define MESH_VERT_MAX (char)18
#define MESH_MAX 82
#define MODEL_MAX 9

struct mesh {
	char a;					/* ATTribute for render */
	char mdl;				/* MoDeL ID */
	char cid;				/* Character ID */
	char shw;				/* SHoW this object? */

	unsigned stroke;		/* stroke color */
	unsigned fill;			/* fill color */
	unsigned texmap[16];	/* texture bits */

	struct polygon poly[MESH_POLY_MAX];	/* polygon faces */
	struct vertex vert[MESH_VERT_MAX];	/* 3D space vertices */
	struct point proj[MESH_VERT_MAX];	/* 2D space vertices */

} meshes[MESH_MAX], models[MODEL_MAX], *rpipe[MESH_MAX];

int rsize = 0;		/* count of objects in render pipeline */
char rnext = '0';	/* next usable ID for render pipeline */

#ifdef NDEBUG
#define ASSERT_MESH(m) ;
#define ASSERT_MODEL(m) ;
#else
#define ASSERT_MESH(m) { \
	if (!m || m < meshes || m >= (meshes+MESH_MAX) || !(m)->cid) { \
		screen(3); \
		if (m) { dump(m, FALSE); } \
		printf("MESH address 0x%x (0x%x - 0x%x)\n", \
			m, meshes, (meshes+MESH_MAX)); \
		printf("ASSERT MESH: %s (%s, %d)\n", #m, __FILE__, __LINE__); \
		quit3d(); \
		exit(1); \
	} \
}

#define ASSERT_MODEL(m) { \
	if (!m || m < models || m >= (models+MODEL_MAX) || !(m)->mdl) { \
		screen(3); \
		if (m) { dump(m, FALSE); } \
		printf("MODEL address 0x%x (0x%x - 0x%x)\n", \
			m, models, (models+MODEL_MAX)); \
		printf("ASSERT MODEL: %s (%s, %d)\n", #m, __FILE__, __LINE__); \
		quit3d(); \
		exit(1); \
	} \
}
#endif

/* solid filled triangle mesh */
#define A_SOLID (char)1

/* wireframe triangle mesh */
#define A_WIRED (char)2

/* solid filled wireframe triangle mesh */
#define A_WIRES (char)3

/* wireframe quad mesh */
#define A_QUADW (char)4

/* texture-mapped quad mesh */
#define A_QUADT (char)5

/* bordered texture-mapped quad mesh */
#define A_QUADB (char)6

/* texture-mapped triangle mesh */
#define A_TEXTA (char)7

/* bordered texture-mapped triangle mesh */
#define A_TEXTB (char)8

/* outlined solid */
#define A_OUTLN (char)9

/* outlined empty */
#define A_OUTLE (char)10

int A_VERTS[] = { 0,
	3, 3, 3,
	4, 4, 4,
	3, 3, 3 };

char *A_NAMES[] = { "EMPTY",
	"SOLID", "WIRED", "WIRES",
	"QUADW", "QUADT", "QUADB",
	"TEXTA", "TEXTB", "OUTLN" };

char A_TEXTURED[] = { FALSE,
	FALSE, FALSE, FALSE,
	FALSE, TRUE, TRUE,
	TRUE, TRUE, FALSE };

char A_WIREFRAME[] = { FALSE,
	FALSE, TRUE, TRUE,
	TRUE, FALSE, TRUE,
	FALSE, TRUE, FALSE };

/* determine if polygon is render-able (wireframes ignore the SHOW flag) */
#define SHOWN(mo,p) ((p)->shw || A_QUADW == (mo)->a || A_WIRED == (mo)->a)
#define HIDDEN(mo,p) (!(p)->shw && A_QUADW != (mo)->a && A_WIRED != (mo)->a)

/* final index of depending on mesh attribute */
#define VERTS_PER_POLY(mo) A_VERTS[(mo)->a]

/* index into vertices array based on index of vertex (0-3) */
#define POLY_VERT_IDX(p,vi) (*((unsigned char*)(p)+vi) >= MESH_VERT_MAX \
	? MESH_VERT_MAX-1 : *((char*)(p)+vi))

/* vertex object by polygon pointer and vertex index */
#define MESH_VERT(mo,p,vi) (mo)->vert[POLY_VERT_IDX(p,vi)]
#define MESH_PROJ(mo,p,vi) (mo)->proj[POLY_VERT_IDX(p,vi)]

/* for-each helper macros to make looping easier / safer */
#define FOREACH_MESH(mo,i) for (i=0, mo=meshes; i < MESH_MAX; i++,mo++)

#define FOREACH_MODEL(mo,i) for (i=0, mo=models; i < MODEL_MAX; i++,mo++)

#define MESH_FOREACH_POLY(mo,p,pi) for (pi = 0, p = (mo)->poly; \
	pi < MESH_POLY_MAX && POLY_NOT_NULL((*p)); pi++,p++)

#define MESH_FOREACH_VERT(mo,v,vi) for (vi = 0, v = (mo)->vert; \
	vi < MESH_VERT_MAX && VERT_NOT_NULL((*v)); vi++,v++)

#define MESH_FOREACH_PROJ(mo,v,vi) for (vi = 0, v = (mo)->proj; \
	vi < MESH_VERT_MAX && VERT_NOT_NULL((*v)); vi++,v++)

#define POLY_FOREACH_VERT(mo,p,v,vi) for (vi = 0, v = &MESH_VERT(mo,p,vi); \
	vi < VERTS_PER_POLY(mo); vi++, v = &MESH_VERT(mo,p,vi))

#define POLY_FOREACH_PROJ(mo,p,v,vi) for (vi = 0, v = &MESH_PROJ(mo,p,vi); \
	vi < VERTS_PER_POLY(mo); vi++, v = &MESH_PROJ(mo,p,vi))

struct edge {
   int RemainingScans;
   int vBeg, vEnd;
   long U, UStep, V, VStep;
   int X, XStep, XDir, XErr, XAdjUp, XAdjDown;
} left, right;

char addpipe(struct mesh*);
char addpoly(struct mesh*, int,int,int, int,int,int, int,int,int, char);
char addquad(struct mesh*, int,int,int, int,int,int, int,int,int, int,int,int);
struct mesh *addmesh(struct mesh*, char);
struct mesh *addmodel(char);
char addvert(struct mesh*, int,int,int);
void checkfaces(struct mesh*);
void circley3d(int,int,int, int, unsigned);
void clearpipe(char);
void delpipe(struct mesh*, char);
int depthcompar(const void *, const void *);
void depthsort(struct mesh*[], int);
void dump(struct mesh*, char);
void edgedump(struct edge*);
char edgefind(struct edge*, struct mesh*, int, int, int, int);
char freemesh(struct mesh*);
char freemodel(struct mesh*);
void frustrum(struct mesh*);
void init3d(void);
void liney3d(int,int, int,int, int,unsigned);
struct mesh *model(char);
void normals(struct mesh*);
void pipeline(char, char, char);
void project(struct mesh*, char);
#define project_x(x,z) ((int)( ((long)(x) << VD) / (z)) + OX)
#define project_y(y,z) (-( ((y) << VD) / (z) ) + OY)
void quit3d(void);
void render(struct mesh*);
void reset(struct mesh*, char, unsigned, unsigned);
void rotatex(struct mesh*, int);
void rotatey(struct mesh*, int);
void rotateyatz(struct mesh*, int, int);
void rotatez(struct mesh*, int);
void scale(struct mesh*, long, long, long);
void show(struct mesh*);
#define texel(texmap,u,v) (texmap[(v)&0xF] >> (u) & 0x1)
void texprint(struct mesh*, char*);
char texture(struct mesh*, int);
void translate(struct mesh*, int,int,int);

/* add to rendering pipeline */
char addpipe(struct mesh *mo)
{
	if (!mo) {
		return TRUE; /* sure */
	}

	if (mo->cid >= rnext) {
		rnext = mo->cid + 1;
	}

	ASSERT_MESH(mo);

	if (rsize >= MESH_MAX) {
		int i = 0;
		do {
			if (!rpipe[i]) {
				rpipe[i] = mo;
				return TRUE;
			}
		} while (++i < MESH_MAX);
		return FALSE;
	}

	rpipe[rsize++] = mo;
	return TRUE;
}

/* add 3D triangle to 3D object and return its index */
char addpoly(struct mesh *mo, int x1,int y1,int z1, int x2,int y2,int z2,
	int x3,int y3,int z3, char border)
{
	char i, v1, v2, v3;

	if (!mo) {
		return MESH_POLY_MAX;
	}

	v1 = addvert(mo, x1,y1,z1);
	v2 = addvert(mo, x2,y2,z2);
	v3 = addvert(mo, x3,y3,z3);

	if (MESH_VERT_MAX == v1 || MESH_VERT_MAX == v2 || MESH_VERT_MAX == v3) {
		return MESH_POLY_MAX;
	}

	for (i = (char)0; i < MESH_POLY_MAX; i++) {

		if (v1 == mo->poly[i].v1 &&
			v2 == mo->poly[i].v2 &&
			v3 == mo->poly[i].v3 &&
			border == mo->poly[i].v4) {
			break; /* already exists */
		}

		if (POLY_IS_NULL(mo->poly[i])) {
			if (1 + i < MESH_POLY_MAX) {
				POLY_MAKE_NULL(mo->poly[1 + i]);
			}
			mo->poly[i].v1 = v1;
			mo->poly[i].v2 = v2;
			mo->poly[i].v3 = v3;
			mo->poly[i].v4 = border;
			break;
		}
	}

	return i;
}

/* add 3D quadrilateral to 3D object and return its index */
char addquad(struct mesh *mo, int x1,int y1,int z1, int x2,int y2,int z2,
	int x3,int y3,int z3, int x4,int y4,int z4)
{
	char v4 = addvert(mo, x4,y4,z4);

	if (!mo) {
		return MESH_POLY_MAX;
	}

	if (MESH_VERT_MAX == v4) {
		return MESH_POLY_MAX;
	}

	return addpoly(mo, x1,y1,z1, x2,y2,z2, x3,y3,z3, v4);
}

/* allocates a new mesh based on a model */
struct mesh *addmesh(struct mesh *model, char id)
{
	static int meshi = 0;
	int starti = meshi;
	struct mesh *mo = 0;

	do { /* find empty mesh slot based on last slot */
		if (++meshi >= MESH_MAX) {
			meshi = 0;
		}

		if (!meshes[meshi].a) {
			mo = &meshes[meshi];
			break;
		}

	} while (meshi != starti);

	if (!mo) { /* recycle mesh slot based on Z distance */
		int d, distance = meshes[0].vert[0].z;
		meshi = 0;
		for (starti = 1; starti < MESH_MAX; starti++) {
			if ((d = meshes[starti].vert[0].z) > distance) {
				meshi = starti;
				distance = d;
			}
		}
		mo = &meshes[meshi];
	}

	if (model) {
		ASSERT_MODEL(model);
		memcpy(mo, model, sizeof(struct mesh));
	}
	mo->cid = id;
	ASSERT_MESH(mo);

	return mo;
}

/* allocates a new model or re-uses existing one */
struct mesh *addmodel(char mdl)
{
	int i;
	struct mesh *m = model(mdl);

	if (!m) {
		for (i = 0; i < MODEL_MAX; i++) {
			if (!models[i].a) {
				m = &models[i];
				m->mdl = mdl;
				m->cid = ' ';
				break;
			}
		}
	}

	ASSERT_MODEL(m);

	return m;
}

/* add 3D vertex to 3D object and return its index */
char addvert(struct mesh *mo, int x, int y, int z)
{
	char i;

	if (!mo) {
		return MESH_VERT_MAX;
	}

	for (i = (char)0; i < MESH_VERT_MAX; i++) {

		if (x == mo->vert[i].x &&
			y == mo->vert[i].y &&
			z == mo->vert[i].z) {
			/* printf("Reusing Vertex %d\n", i); */
			break; /* already exists */
		}

		if (VERT_IS_NULL(mo->vert[i])) {
			/* printf("Adding Vertex %d: %d, %d, %d\n", i, x, y, z); */
			if (1 + i < MESH_VERT_MAX) {
				VERT_MAKE_NULL(mo->vert[1 + i]);
			}
			mo->vert[i].x = x;
			mo->vert[i].y = y;
			mo->vert[i].z = z;
			break;
		}
	}

	return i;
}

/* perform backface culling; must be called AFTER normals() */
void checkfaces(struct mesh *mo)
{
	int vx, vy, vz;		/* viewing vector (line of sight) */
	long dotprod;		/* dot product of viewing vector and normal */
	struct polygon *p;
	int i;

	for (i = 0, p = mo->poly; i < MESH_POLY_MAX && POLY_NOT_NULL((*p)); i++,p++) {

		/* since all coordinates are in world space:
			viewing vector is 0,0,0 -> p->x1,y1,z1 */
		vx = mo->vert[p->v1].x;
		vy = mo->vert[p->v1].y;
		vz = mo->vert[p->v1].z;

		/* (u->x * v->x) + (u->y * v->y) + (u->z * v->z) */
		dotprod = (long)p->nx*vx + (long)p->ny*vy + (long)p->nz*vz;

		/* printf("Dot Product = %ld\n", dotprod); */

		if (dotprod > 0) {
			p->shw = TRUE;
		} else {
			p->shw = FALSE;
		}
	}
}

/* draw a flat (2d) circle on the Y plane at a location in 3d */
void circley3d(int x, int y, int z, int r, unsigned c)
{
	/* adjust degree increment for granularity (lower = slower = finer) */
	int deg1 = 0, deg2 = 23, deginc = 30;
	int xo, yo;
	int x2, y2, z2;
	int x1, y1, z1 = z + MUL_COS_DEG(r, deg1);

	if (x < -YON || x > YON || z < 1 || z - r > YON || z + r < HITHER) {
		return;
	}

	xo = x1 = project_x(x + MUL_SIN_DEG(r, deg1), z1);
	yo = y1 = project_y(y, z1);

	for ( ; deg2 < 360; deg2 += deginc) {

		z2 = z + MUL_COS_DEG(r, deg2);
		if (z2 < 1) {
			continue;
		}
		x2 = project_x(x + MUL_SIN_DEG(r, deg2), z2);
		y2 = project_y(y, z2);

		line(x1,y1, x2,y2, c);

		x1 = x2;
		y1 = y2;
		z1 = z2;
		deg1 = deg2;
	}

	line(x1,y1, xo, yo, c);
}

/* clear rendering pipeline */
void clearpipe(char free)
{
	if (free) {
		int i = 0;
		for ( ; i < rsize; i++) {
			freemesh(rpipe[i]);
			rpipe[i] = 0;
		}
	}

	rsize = 0;
	rnext = '0';
}

/* delete object from rendering pipeline */
void delpipe(struct mesh *mo, char free)
{
	int i = 0;
	if (free) {
		for ( ; i < rsize; i++) {
			if (rpipe[i] == mo) {
				rpipe[i] = 0;
			}
		}
	} else {
		for ( ; i < rsize; i++) {
			if (rpipe[i] == mo) {
				freemesh(rpipe[i]);
				rpipe[i] = 0;
			}
		}
	}
}

/* used as compar function parameter to qsort() */
int depthcompar(const void *a, const void *b)
{
	struct mesh *pa = *(struct mesh**)a;
	struct mesh *pb = *(struct mesh**)b;
	if (pa->cid == pb->cid) {
		return pa->mdl - pb->mdl;
	}
	return pb->vert[0].z - pa->vert[0].z;
}

/* depth sort an array of POINTERS to 3D objects */
void depthsort(struct mesh *a[], int size)
{
	qsort(a, size, sizeof(struct mesh*), depthcompar);
}

/* dump debug output of 3D object */
void dump(struct mesh *mo, char projected)
{
	int i, vc, tc, vi, pi, size;
	struct polygon *p;
	struct vertex *v;
	struct point *pt;
	char *name = "UNKNOWN";

	MESH_FOREACH_VERT(mo,v,vi);
	vc = vi;

	MESH_FOREACH_POLY(mo,p,pi);
	tc = pi;

	size = sizeof(struct mesh) -
		((MESH_POLY_MAX - tc) * sizeof(struct polygon)) -
		((MESH_VERT_MAX - vc) * sizeof(struct vertex) * 2);

	if (mo->a >= 0 && mo->a <= 9) {
		name = A_NAMES[mo->a];
	}

	for (i = 0; i < MESH_MAX; i++) {
		if (mo == &meshes[i]) {
			printf("%s MESH%d %c%c (%d vert, %d poly, %d/%d b):\n",
				name, i, mo->mdl, mo->cid, vc, tc, size, sizeof(struct mesh));
			break;
		}
	}
	if (i >= MESH_MAX) {
		for (i = 0; i < MODEL_MAX; i++) {
			if (mo == &models[i]) {
				printf("%s MODEL%d %c%c (%d vert, %d poly, %d/%d b):\n",
					name, i, mo->mdl, mo->cid, vc, tc, size, sizeof(struct mesh));
				break;
			}
		}
		if (i >= MODEL_MAX) {
			printf("%s %c%c (%d vert, %d poly, %d/%d b):\n",
				name, mo->mdl, mo->cid, vc, tc, size, sizeof(struct mesh));
		}
	}

	MESH_FOREACH_POLY(mo,p,pi) {
		printf(" %c %02d:", SHOWN(mo,p) ? '*' : ' ', (1+pi));

		if (projected) {
			POLY_FOREACH_PROJ(mo,p,pt,vi) {
				if (vi > 3) {
					printf("[VTX ERROR %d]", vi);
					break;
				}
				if (VERT_IS_NULL(*v)) {
					printf("[VTX NULL %d]", vi);
					break;
				}
				for (i = 0; i < MESH_VERT_MAX; i++) {
					if (pt == &mo->proj[i]) {
						break;
					}
				}
				printf(" %c(%d,%d)", (char)(65+i), pt->x, pt->y);
			}
		} else {
			POLY_FOREACH_VERT(mo,p,v,vi) {
				if (vi > 3) {
					printf("[VTX ERROR %d]", vi);
					break;
				}
				if (VERT_IS_NULL(*v)) {
					printf("[VTX NULL %d]", vi);
					break;
				}
				for (i = 0; i < MESH_VERT_MAX; i++) {
					if (v == &mo->vert[i]) {
						break;
					}
				}
				printf(" %c(%d,%d,%d)", (char)(65+i), v->x, v->y, v->z);
			}
		}
		puts("");
	}

	if (vc > tc * 3) {
		/* weird if there are MORE than 3x as many vertices as polygons */
		if (projected) {
			MESH_FOREACH_PROJ(mo,pt,vi) {
				printf(" V %02d: %d, %d\n", vi, pt->x, pt->y);
			}
		} else {
			MESH_FOREACH_VERT(mo,v,vi) {
				printf(" V %02d: %d, %d, %d\n", vi, v->x, v->y, v->z);
			}
		}
	}
}

void edgedump(struct edge *e)
{
	printf("%sEdge V%d - V%d\n",
		(e == &left ? "Left " : (e == &right ? "Right " : "")),
		e->vBeg, e->vEnd);

	printf("U/V: %d,%d (0x%lx, 0x%lx) + 0x%lx,0x%lx\n",
		ROUND_FX(e->U), ROUND_FX(e->V), e->U, e->V, e->UStep, e->VStep);
	printf("  X: %d + (%d * %d) [%d, %d, %d]\n",
		e->X, e->XDir, e->XStep, e->XErr, e->XAdjUp, e->XAdjDown);
}

/* finds the first edge in a polygon starting from a specific index */
char edgefind(struct edge *eout, struct mesh *mo, int pi, int dir,
	int vi, int MaxVert)
{
	struct polygon *p = &mo->poly[pi];
	struct point *pStart = &MESH_PROJ(mo,p,vi);
	struct point *pNext = 0;
	int nextvi, Width;
	long HeightFx;

	if (pi >= MESH_POLY_MAX || POLY_IS_NULL(*p) || POINT_IS_NULL(*pStart)) {
		return FALSE;
	}

	for ( ; vi != MaxVert; pStart = pNext, vi = nextvi) {

		nextvi = vi + dir;
		if (nextvi < 0) {
			nextvi = VERTS_PER_POLY(mo) - 1;
		} else if (nextvi >= VERTS_PER_POLY(mo)) {
			nextvi = 0;
		}

		pNext = &MESH_PROJ(mo,p,nextvi);

		if ((eout->RemainingScans = pNext->y - pStart->y) != 0) {

			HeightFx = INT_FX(eout->RemainingScans);
			eout->vBeg = vi;
			eout->vEnd = nextvi;

			eout->U = VERT_U_FX(vi);
			eout->UStep = DIV_FX(VERT_U_FX(nextvi) - eout->U, HeightFx);

			eout->V = VERT_V_FX(vi);
			eout->VStep = DIV_FX(VERT_V_FX(nextvi) - eout->V, HeightFx);

			/* Set up Bresenham-style variables for dest X stepping */
			eout->X = pStart->x;
			if ((Width = (pNext->x - pStart->x)) < 0) {
				/* Set up for drawing right to left */
				eout->XDir = -1;
				Width = -Width;
				eout->XErr = 1 - eout->RemainingScans;
				eout->XStep = -(Width / eout->RemainingScans);
			} else {
				/* Set up for drawing left to right */
				eout->XDir = 1;
				eout->XErr = 0;
				eout->XStep = Width / eout->RemainingScans;
			}

			eout->XAdjUp = Width % eout->RemainingScans;
			eout->XAdjDown = eout->RemainingScans;

			return TRUE;
      }
   }

	return FALSE;
}

char freemesh(struct mesh *mo)
{
	int i;
	for (i = 0; i < MESH_MAX; i++) {
		if (mo == &meshes[i]) {
			meshes[i].a = 0;
			return TRUE;
		}
	}
	return FALSE;
}

char freemodel(struct mesh *mo)
{
	int i;
	for (i = 0; i < MODEL_MAX; i++) {
		if (mo == &models[i]) {
			models[i].a = 0;
			return TRUE;
		}
	}
	return FALSE;
}

/* determines if object is within viewing frustrum */
void frustrum(struct mesh *mo)
{
	struct vertex *v;	/* vertex (point) pointer */
	int vi;				/* vetex index */

	MESH_FOREACH_VERT(mo,v,vi) {
		if (v->z < HITHER || v->z > YON) {
			mo->shw = FALSE;
			return;
		}
	}

	/* X and Y are checked by project() after converting to screen space */

	mo->shw = TRUE;
}

/* allocates and clears resources for 3D engine */
void init3d(void)
{
	int i;
	struct mesh *m;

	memset(rpipe, 0, sizeof(rpipe));
	rsize = 0;

	memset(&left, 0, sizeof(struct edge));

	memset(&right, 0, sizeof(struct edge));

	memset(meshes, 0, sizeof(meshes));
	FOREACH_MESH(m,i) {
		reset(m, 0, 0, 0);
	}

	memset(models, 0, sizeof(models));
	FOREACH_MODEL(m,i) {
		reset(m, 0, 0, 0);
	}
}

/* draws a 3D line at a level on the Y plane between two X,Z points */
void liney3d(int x1,int z1, int x2,int z2, int y,unsigned c)
{
	if (clipline(&x1,&z1, &x2,&z2, -YON,HITHER,YON,YON)) {
		line(project_x(x1,z1), project_y(y,z1),
			project_x(x2,z2), project_y(y,z2), c);
	}
}

/* find model by its ID or return null */
struct mesh *model(char mdl)
{
	int i;
	for (i = 0; i < MODEL_MAX; i++) {
		if (models[i].a && models[i].mdl == mdl) {
			return &models[i];
		}
	}
	return 0;
}

/* turn off visibility of both object and all its faces */
void hide(struct mesh *mo)
{
	struct polygon *p;			/* polygon (triangle) pointer */
	int i;						/* poly index */

	MESH_FOREACH_POLY(mo,p,i) {
		p->shw = FALSE;
	}

	mo->shw = TRUE;
}

/* calculate normals of all triangles in an object */
void normals(struct mesh *mo)
{
	struct polygon *p;	/* polygon (triangle) pointer */
	int i;				/* poly index */
	int ux, uy, uz;
	int vx, vy, vz;
	long lnx, lny, lnz; /* 32-bit raw normal to handle overflow */

	/* CROSS PRODUCT NOTE: not commutative! (vertex order matters) */

	MESH_FOREACH_POLY(mo,p,i) {

		/* create U vector from vertex 1 to 3 (left counter-clockwise) */
		ux = mo->vert[p->v3].x - mo->vert[p->v1].x;
		uy = mo->vert[p->v3].y - mo->vert[p->v1].y;
		uz = mo->vert[p->v3].z - mo->vert[p->v1].z;

		/* create V vector from vertex 1 to 2 (right clockwise) */
		vx = mo->vert[p->v2].x - mo->vert[p->v1].x;
		vy = mo->vert[p->v2].y - mo->vert[p->v1].y;
		vz = mo->vert[p->v2].z - mo->vert[p->v1].z;

		/* calculate cross product (U x V) for NORMAL vector
			(the normal vector is perpendicular and thus "facing out") */
		lnx = uy*vz - uz*vy;
		lny = -( ux*vz - uz*vx );
		lnz = ux*vy - uy*vx;

		/* normalize into signed 8-bit range (-128 to +127) */
		while (lnx < -128 || lnx > 127
			|| lny < -128 || lny > 127
			|| lnz < -128 || lnz > 127) {
			lnx >>= 1;
			lny >>= 1;
			lnz >>= 1;
		}

		p->nx = (char)lnx;
		p->ny = (char)lny;
		p->nz = (char)lnz;

		/* printf("Normalized Normal: %d,%d,%d\n", p->nx, p->ny, p->nz); */
	}
}

/* draws an outline of the 2D projected shape */
void outline(struct mesh *mo)
{
	char polyused[MESH_POLY_MAX];
	char outline[MESH_VERT_MAX];
	char va, vb;
	struct point *p1, *p2;
	int i, j, pi, outsize, polyleft = 0;
	struct polygon *p;

	/* count visible polygons; all of these will be outlined */
	MESH_FOREACH_POLY(mo,p,pi) {
		if (p->shw) {
			polyleft++;
			polyused[pi] = FALSE;
		} else {
			polyused[pi] = TRUE;
		}
	}

	/* loop while shapes remain */
	while (polyleft) {

		outsize = 0;

		/* use first VISIBLE polygon for initial shape */
		MESH_FOREACH_POLY(mo,p,pi) {
			if (!polyused[pi]) {
				polyused[pi] = TRUE;
				polyleft--;
				outline[0] = p->v1;
				outline[1] = p->v2;
				outline[2] = p->v3;
				outsize = 3;
				break;
			}
		}

		outline[outsize] = outline[0];
		for (i = 0; polyleft && i < outsize; i++) {

			va = outline[i];
			vb = outline[1+i];

			/* find connected polygon */
			MESH_FOREACH_POLY(mo,p,pi) {

				if (polyused[pi]) {
					continue;
				}

				/* any connected polygon MUST have 2 matching vertices */
				if ((p->v1 == va && p->v2 == vb) ||
					(p->v1 == vb && p->v2 == va)) {
					vb = p->v3;
				} else if ((p->v1 == va && p->v3 == vb) ||
							(p->v1 == vb && p->v3 == va)) {
					vb = p->v2;
				} else if ((p->v2 == va && p->v3 == vb) ||
							(p->v2 == vb && p->v3 == va)) {
					vb = p->v1;
				} else {
					continue;
				}

				/* mark poly so we don't test it again */
				polyused[pi] = TRUE;
				polyleft--;

				/* insert new vertex */
				i++;
				for (j = outsize; j > i; j--) {
					outline[j] = outline[j-1];
				}
				outline[i] = vb;
				outsize++;
				outline[outsize] = outline[0];

				/* break to outer loop to restart poly search */
				i -= 2;
				break;
			} /* foreach (visible polygons) */

		} /* for (all edges in shape) */

		/* draw shape from line to line */
		p2 = &mo->proj[outline[0]];
		for (i = 1; i < outsize; i++) {
			p1 = p2;
			p2 = &mo->proj[outline[i]];
			line(p1->x, p1->y, p2->x, p2->y, mo->stroke);
		}
		p1 = &mo->proj[outline[0]];
		line(p2->x, p2->y, p1->x, p1->y, mo->stroke);

	} /* while (polyleft) */
}

/* fixed rendering pipeline */
void pipeline(char recull, char reproject, char redraw)
{
	int i = 0;

	if (recull && reproject && redraw) { /* all together now! */
		depthsort(rpipe, rsize);

		for ( ; i < rsize; i++) {

			checkfaces(rpipe[i]);

			frustrum(rpipe[i]);

			if (rpipe[i]->shw) {

				project(rpipe[i], TRUE);

				render(rpipe[i]);

			}
		}

		return;
	}

	if (recull) {
		depthsort(rpipe, rsize);

		for (i = 0 ; i < rsize; i++) {

			checkfaces(rpipe[i]);

			frustrum(rpipe[i]);
		}
	}

	if (reproject) {
		for (i = 0 ; i < rsize; i++) {

			if (rpipe[i]->shw) {
				project(rpipe[i], TRUE);
			}
		}
	}

	if (redraw) {
		for (i = 0; i < rsize; i++) {
			if (rpipe[i]->shw) {
				render(rpipe[i]);
			}
		}
	}
}

/* project 3D to 2D by dividing X and Y by Z ( X' = X*VD/Z, Y' = -(Y*VD/Z) ) */
void project(struct mesh *mo, char clip)
{
	struct vertex *v;
	int z, vi;

	MESH_FOREACH_VERT(mo,v,vi) {

		z = v->z;

		if (!z) {
			mo->proj[vi].x = mo->proj[vi].y = 0;
			continue;
		}

		mo->proj[vi].x = project_x(v->x, z);
		mo->proj[vi].y = project_y(v->y, z);
	}

	/* clip off-screen polygons */
	if (clip) {
		struct polygon *p;
		MESH_FOREACH_POLY(mo,p,vi) {
			if (mo->vert[p->v1].z <= 0 ||
				mo->vert[p->v2].z <= 0 ||
				mo->vert[p->v3].z <= 0 ||
				((unsigned)mo->proj[p->v1].x > X_MAX &&
				(unsigned)mo->proj[p->v2].x > X_MAX &&
				(unsigned)mo->proj[p->v3].x > X_MAX) ||
				((unsigned)mo->proj[p->v1].y > Y_MAX &&
				(unsigned)mo->proj[p->v2].y > Y_MAX &&
				(unsigned)mo->proj[p->v3].y > Y_MAX)) {
				p->shw = FALSE;
			}
		}
	}
}

/* frees resources used by 3D engine */
void quit3d(void)
{
	init3d();
}

/* draw object */
void render(struct mesh *mo)
{
	struct polygon *p;
	int pi;
	int textured = A_TEXTURED[mo->a];
	int framed = A_WIREFRAME[mo->a];
	int quad = 4 == VERTS_PER_POLY(mo);

	color(mo->stroke, mo->fill);

	if (A_OUTLE == mo->a) {
		outline(mo);
	} else {
		MESH_FOREACH_POLY(mo,p,pi) {

			if (HIDDEN(mo,p)) {
				continue;
			}

			if (textured && !texture(mo, pi)) {
				continue;
			}

			if (framed) {
				line(mo->proj[p->v1].x, mo->proj[p->v1].y,
					mo->proj[p->v2].x, mo->proj[p->v2].y, cga_stro);
				line(mo->proj[p->v2].x, mo->proj[p->v2].y,
					mo->proj[p->v3].x, mo->proj[p->v3].y, cga_stro);

				if (quad) {
					line(mo->proj[p->v3].x, mo->proj[p->v3].y,
						mo->proj[p->v4].x, mo->proj[p->v4].y, cga_stro);
					line(mo->proj[p->v4].x, mo->proj[p->v4].y,
						mo->proj[p->v1].x, mo->proj[p->v1].y, cga_stro);

				} else {
					line(mo->proj[p->v3].x, mo->proj[p->v3].y,
						mo->proj[p->v1].x, mo->proj[p->v1].y, cga_stro);
				}
			} else if (!textured) {

				border(p->v4);

				trifill(mo->proj[p->v1].x, mo->proj[p->v1].y,
					mo->proj[p->v2].x, mo->proj[p->v2].y,
					mo->proj[p->v3].x, mo->proj[p->v3].y, cga_fill);
			}
		}

		if (A_OUTLN == mo->a) {
			outline(mo);
		}
	}
}

/* initialize 3D object */
void reset(struct mesh *mo, char a, unsigned stroke, unsigned fill)
{
	mo->a = a;
	/* mo->mdl set by addmodel() */
	/* mo->cid set by addmesh() */
	mo->shw = TRUE;

	mo->stroke = stroke;
	mo->fill = fill;

	POLY_MAKE_NULL(mo->poly[0]);
	VERT_MAKE_NULL(mo->vert[0]);
	POINT_MAKE_NULL(mo->proj[0]);
}

/* rotate around X axis by degrees */
void rotatex(struct mesh *mo, int deg)
{
	struct vertex *v;
	int vi;

	if (mo && deg) {
		MESH_FOREACH_VERT(mo,v,vi) {
			rotatefx(&v->y, &v->z, deg);
		}
		normals(mo);
	}
}

/* rotate around Y axis by degrees */
void rotatey(struct mesh *mo, int deg)
{
	struct vertex *v;
	int vi;

	while (deg >= 360) {
		deg -= 360;
	}

	while (deg < 0) {
		deg += 360;
	}

	if (mo && deg) {
		MESH_FOREACH_VERT(mo,v,vi) {
			rotatefx(&v->x, &v->z, deg);
		}
		normals(mo);
	}
}

/* rotate around Y axis by degrees at a different origin*/
void rotateyatz(struct mesh *mo, int deg, int z)
{
	struct vertex *v;
	int vi;
	int vz;

	if (mo && deg) {
		MESH_FOREACH_VERT(mo,v,vi) {
			vz = v->z - z;
			rotatefx(&v->x, &vz, deg);
			v->z = vz + z;
		}
		normals(mo);
	}
}

/* rotate around Z axis by degrees */
void rotatez(struct mesh *mo, int deg)
{
	struct vertex *v;
	int vi;

	if (mo && deg) {
		MESH_FOREACH_VERT(mo,v,vi) {
			rotatefx(&v->y, &v->x, deg);
		}
		normals(mo);
	}
}

/* resizes using 18.14 fixed point math */
void scale(struct mesh *mo, long sx, long sy, long sz)
{
	struct vertex *v;
	int vi;

	if (mo && FX_1_0 != sx || FX_1_0 != sy || FX_1_0 != sz) {
		MESH_FOREACH_VERT(mo,v,vi) {
			v->x = (int)MUL_FRAC(v->x, sx);
			v->y = (int)MUL_FRAC(v->y, sy);
			v->z = (int)MUL_FRAC(v->z, sz);
		}
	}
}

/* turn on visibility of both object and its faces */
void show(struct mesh *mo)
{
	struct polygon *p;
	int pi;

	if (mo) {
		MESH_FOREACH_POLY(mo,p,pi) {
			p->shw = TRUE;
		}
	}

	mo->shw = TRUE;
}

void texprint(struct mesh *mo, char *ch)
{
	unsigned char far *c1 = bioschar(ch[0]);
	unsigned char far *c2 = bioschar(ch[1]);
	int x, y;

	memset(mo->texmap, 0, sizeof(mo->texmap));

	if (!ch[1]) { /* single character, center it */
		for (y = 0; y < 8; y++) {
			for (x = 4; x < 12; x++) {
				if (FONT_BIT(c1,x-4,y)) {
					mo->texmap[y+4] |= (1 << x);
				}
			}
		}
	} else { /* two characters */
		for (y = 0; y < 8; y++) {
			for (x = 0; x < 8; x++) {
				if (FONT_BIT(c1,x,y)) {
					mo->texmap[y+4] |= (1 << x);
				}
			}
			for (x = 8; x < 16; x++) {
				if (FONT_BIT(c2,x-8,y)) {
					mo->texmap[y+4] |= (1 << x);
				}
			}
		}
	}
}

void texputc(struct mesh *mo, char ch)
{
	unsigned char far *fbits = bioschar(ch);
	int x, y;

	memset(mo->texmap, 0, sizeof(mo->texmap));

	for (y = 1; y < 16; y++) {
		for (x = 1; x < 16; x++) {
			if (FONT_BIT(fbits,(x-1)>>1,(y-1)>>1)) {
				mo->texmap[y] |= (1 << (x+1));
			}
		}
	}
}

/* DDA fast / affine texture mapping based on Michael Abrash's XSharp 21 */
char texture(struct mesh *mo, int pi)
{
	struct polygon *p = &mo->poly[pi];
	int MinY = mo->proj[p->v1].y;
	int MaxY = MinY;
	int vi, Y, MinVert = 0, MaxVert = 0;
	struct point *pt;
	unsigned *texmap = mo->texmap;

	POLY_FOREACH_PROJ(mo,p,pt,vi) {
		Y = pt->y;
		if (Y < MinY) {
			MinY = Y;
			MinVert = vi;
		}
		if (Y > MaxY) {
			MaxY = Y;
			MaxVert = vi;
		}
	}

	/* Reject flat (0-pixel-high) polygons */
	if (MinY >= MaxY) {
		return FALSE;
	}

	edgefind(&left, mo, pi, -1, MinVert, MaxVert);

	edgefind(&right, mo, pi, 1, MinVert, MaxVert);

	for (Y = MinY; Y < 200 && Y <= MaxY; Y++) {
		long WidthFx = INT_FX(right.X - left.X);

		/* DRAW SCANLINE */
		if (Y >= 0 && right.X >= 0 && left.X < 320 && WidthFx > 0) {
			int X = left.X, X2 = right.X, dist;
			long U = left.U, V = left.V;
			long UStep = DIV_FX(right.U - U, WidthFx);
			long VStep = DIV_FX(right.V - V, WidthFx);
			unsigned char far *p = cga_vbuf + cga_line[Y] + (X >> 2);

			/* U += UStep >> 1;
			V += VStep >> 1; */

			if (X < 0) {
				U += MUL_FX(UStep, INT_FX(0 - X));
				V += MUL_FX(VStep, INT_FX(0 - X));
				X = 0;
				p = cga_vbuf + cga_line[Y];
			}

			/* calculate distance to end of the scanline */
			if (X2 > X_MAX) {
				X2 = X_MAX;
			}
			dist = X2 - X + 1;

			for ( ; X <= X2; X++) {

				int m = cga_mask[X&3];
				p = cga_vbuf + cga_line[Y] + (X >> 2);

				if (texel(texmap,ROUND_FX(U),ROUND_FX(V))) {
					*p = *p & ~m | (mo->stroke & m);
				} else {
					*p = *p & ~m | (mo->fill & m);
				}

				U += UStep;
				V += VStep;
			}
		}

		/* LEFT EDGE step */
		if (0 == --left.RemainingScans) {
			if (!edgefind(&left, mo, pi, -1, left.vEnd, MaxVert)) {
				break;
			}
		} else {
			left.U += left.UStep;
			left.V += left.VStep;
			left.X += left.XStep;

			if ((left.XErr += left.XAdjUp) > 0) {
				left.X += left.XDir;
				left.XErr -= left.XAdjDown;
			}
		}

		/* RIGHT EDGE step */
		if (0 == --right.RemainingScans) {
			if (!edgefind(&right, mo, pi, 1, right.vEnd, MaxVert)) {
				break;
			}
		} else {
			right.U += right.UStep;
			right.V += right.VStep;
			right.X += right.XStep;

			if ((right.XErr += right.XAdjUp) > 0) {
				right.X += right.XDir;
				right.XErr -= right.XAdjDown;
			}
		}
	}

	return TRUE;
}

/* moves an object */
void translate(struct mesh *mo, int tx, int ty, int tz)
{
	struct vertex *v;
	int vi;

	MESH_FOREACH_VERT(mo,v,vi) {
		v->x += tx;
		v->y += ty;
		v->z += tz;
	}
}

#endif
